package kgame5.kgu.ai.astar {
import kgame5.kutil.T;
import kgame5.kutil.Util;

import flash.utils.getTimer;

/**
 * @author kk
 * 这个接受的是一个2维数组,返回的也是一个2维数组，
40*40格子，寻找路径时间
---算法描述----
1,起始点A，加入openList
启动循环，如下。结束条件，openList为空，或到达了目标点
2,从openList里取出F最小的一点X，放入clostList
3,检查X点周围的相邻的节点XX，
	如果这些点在clostList里，忽略
	如果这些点在openList里，则
		看一下新的F值是否比老的要小，如果小，则更新，否则不处理
	如果这些点不在openList里，则加入，并计算F=G+H

---出过的错误----，
1 createNode()里的updateNode()之后，没有return,导致持续的在加东西。
2，addOpen(node)代码之后还有一个openList.push(node),导致同样东西被加了两次
3,计算cost的时候，我用的是isStringht判断，然后+10或者 +14。不如直接+10或+14效率高
4,曾经犯过的错误，Array.sortOn(["F",Array.NUMERIC]).应该是Array.sortOn(["F"],[Array.NUMERIC])
 */
public class AStar {

	public static const COST_XIE:int=14;//斜线cost
	public static const COST_ZHI:int=10;//直线cost

	private var a2Map : Array;//一个二维数组
	
	private var openList : Array;//这样做是因为需要排序，找到最小的来处理
	private var a2Open : Array;//这些是为了查询是否节点在openList中，这样根据名字查询很快
	private var a2Close : Array;//这个标志是在closeList里
	
	private var CC : int;
	private var RC : int;

	private var startNode : AStarNode;
	private var endNode : AStarNode;//结果，这个是用来标识是否有了结果了的
	private var endCol : int,endRow : int;
	
	private var _bNeedSort:Boolean=true;//是否真的需要排序，降低排序时间用的,有的时候并不需要排序
	
	private var _startTimeMS:int;
	private var _durTimeMS:int;
	
	public function AStar(a2Map : Array) {
		this.a2Map = a2Map;
		
		RC = a2Map.length;
		CC = a2Map[0].length;
	}

	public function getDurMS():int{
		return _durTimeMS;
	}
	
	//返回的是一个一维数组[col,row,col,row,col,row]
	public function SearchX(startCol : int,startRow : int,endCol : int,endRow : int) : Array {
		T.p("Search", startCol, startRow, endCol, endRow);
		
		_startTimeMS=getTimer();
		
		//超出范围的不处理
		if(isOutBound(endCol,endRow)||isOutBound(startCol,startRow)){
			return null;
		}
		
		//目标是障碍物的不处理
		if(isBlock(endCol,endRow)||isBlock(startCol,startRow)){
			return null;
		}
		
		//---初始化环境
		startNode = new AStarNode();
		startNode.col = startCol;
		startNode.row = startRow;
		
		endNode=null;//保存结果用的
		this.endCol = endCol;
		this.endRow = endRow;
		
		openList = new Array();
		
		a2Open = Util.NewArray2_Obj(RC, CC);
		a2Close = Util.NewArray2_Obj(RC, CC);//这个保存closeList,便于查找
		
		//--1,把节点a放入到openList
		openList.push(startNode);
		
		_bNeedSort=false;
		
		//--2,
		while(openList.length > 0) {
			//openList不为空，就继续处理
			//T.p("----------处理一次-------------",openList.length);
			//1,排序一下
			if(_bNeedSort){
				//var tt:int=getTimer();
				openList.sortOn(["F"],[Array.NUMERIC]);//f从小到大排序
				//T.p("耗时",getTimer()-tt);
				_bNeedSort=false;
			}else{
				//T.p("------不需要排序");
			}
			
			//2,取出f值最小的节点
			var node : AStarNode = openList.shift() as AStarNode;
			
			//3,加入到closeList里
			addClose(node);
			
			//4,查找它周围的8个点
			find8(node);
			
			//4,如果openList里包含了目标，则结束
			if(endNode != null) {
				break;
			}
			//T.p("-----------一次处理完毕");
		}
		
		//没找到结果，openList空了
		if(endNode==null){
			_durTimeMS=getTimer()-_startTimeMS;
			return null;
		}
		
		//--3,得出路径
		var aResult : Array = new Array();
		
		
		aResult.push(endNode.row);
		aResult.push(endNode.col);
		
		var myParent : AStarNode = endNode.parent;
		
		while(myParent != null) {
			
			aResult.push(myParent.row);
			aResult.push(myParent.col);
			
			myParent = myParent.parent;
		}
		
		_durTimeMS=getTimer()-_startTimeMS;
		
		aResult.reverse();//从起始点到出发点
		
		return aResult;
	}

	private function createNode(col : int,row : int,parent : AStarNode,cost:int) {
		
		//此点是否可达
		if(canReach(parent.col,parent.row,col,row)==false){
			return;
		}
		
		//如果在clostList里就不用找了
		if(isInClose(col, row)) {
			return;
		}
		
		//已经在open表里有了，则更新
		var oldNode : AStarNode = findOpen(col, row);
		if(oldNode != null) {
			updateNode(oldNode, parent, cost);//注意这个parent是testParent
			return;
		}
		
		//-如果不在openList里，才创建新的
		var node : AStarNode = new AStarNode();
		node.col = col;
		node.row = row;
		
		node.parent = parent;
		
		//G
		//if(parent != null) {
		node.G = parent.G + cost;	
		//}
		
		//H
		node.H = (Math.abs(col - endCol) + Math.abs(row - endRow)) * COST_ZHI;
		
		//F
		node.F = node.G + node.H;
		
		//加入到openList中（注意opentTalbe和bNeedSort需要更新）
		addOpen(node);//注意有新的加入是要排序的
	
		//看是否结束
		if(node.col == endCol && node.row == endRow) {
			endNode = node;
		}
	}

	private function updateNode(node : AStarNode,testParent : AStarNode,cost:int) {
		
		var newG:int=testParent.G + cost;
		
		if( node.G >newG) {
			node.G = newG;
			node.parent = testParent;
			
			this._bNeedSort=true;
		}
	}

	//找到周围的8个
	public function find8(node : AStarNode) {
	
		createNode(node.col, node.row - 1, node, COST_ZHI);
		createNode(node.col, node.row + 1, node, COST_ZHI);
		createNode(node.col - 1, node.row, node, COST_ZHI);
		createNode(node.col + 1, node.row, node, COST_ZHI);
		
		createNode(node.col - 1, node.row - 1, node, COST_XIE);
		createNode(node.col + 1, node.row + 1, node, COST_XIE);
		createNode(node.col - 1, node.row + 1, node, COST_XIE);
		createNode(node.col + 1, node.row - 1, node, COST_XIE);
	}

	
	
	//一个格子临近的8个格子，能否到达
	private function canReach(startCol : int,startRow : int,endCol : int,endRow : int) : Boolean {
		//如果是边界，则返回
		if(isOutBound(endCol, endRow)) {
			return false;
		}
		
		if(isBlock(endCol, endRow)) {
			//是障碍物
			return false;
		}
		
		//如果是位于斜向，则要考虑中间是否有障碍物
		if(startCol != endCol && startRow != endRow) {
			if(isBlock(startCol, endRow) || isBlock(endCol, startRow)) {
				return false;
			}
		}
		return true;
	}

	private function isBlock(col : int,row : int) : Boolean {
		return (a2Map[row][col] != 0);
	}

	private function isOutBound(col : int,row : int) : Boolean {
		return (col < 0 || col > CC - 1 || row < 0 || row > RC - 1) ;
	}

	//
	private function isInClose(col : int,row : int) : Boolean {
		//T.p("isInClose",col,row);
		return a2Close[row][col] != null;
	}

	private function addOpen(node : AStarNode) {
		
		openList.push(node);//注意要排序的
		
		a2Open[node.row][node.col]=node;
		
		this._bNeedSort=true;
	}

	private function removeOpen(node : AStarNode) {
		a2Open[node.row][node.col]=null;
		
	}
	
	//isInOpen
	private function findOpen(col : int,row : int) : AStarNode {
		return a2Open[row][col];
	}

	//这个而就隐含表示了从openList中移除了,因为用的是openList.pop()，所以不用删除它
	private function addClose(node : AStarNode) {
		removeOpen(node);
		a2Close[node.row][node.col] = node;
	}
}//end of class
}
